<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>插值查找</title>
  </head>

  <body>
    <script>
      /*
       * 插值查找，将二分查找的点改进为 mid=left+(target-array[left])/(array[right]-array[left])*(right-left)，思路：
       * 1.基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。
       *
       * 前提条件：
       * 1. 数组必须是有序的（递增/递减）
       * 2. 左右边有界
       */
      var insertionArr = [1, 2, 3, 4, 5, 6];
      var target = 4;
      console.log(insertionSearch(insertionArr, target));

      /*
       * array: 被查找数组
       * target：查找的目标值
       */
      function insertionSearch(array, target) {
        var left = 0, //左侧索引值
          right = array.length - 1; //右侧索引值

        while (left <= right) {
          //循环到什么时候结束呢？ 我们循环的过程中， low 和 higt 两个值会逐渐逼近
          var mid =
            left +
            ((target - array[left]) / (array[right] - array[left])) *
              (right - left); //中间索引
          if (target == array[mid]) {
            //判断 中间值是否等于 我们要查的那个数，如果等于，那就找到了，直接返回
            return mid;
          } else if (target < array[mid]) {
            //判断 target 是否 < 中间值， 如果小于  说明我们要找的数，在左边那块
            right = mid - 1;
          } else if (target > array[mid]) {
            //判断 target 是否 > 中间值， 如果小于  说明我们要找的数，在右边那块
            left = mid + 1;
          }
        }

        return -1; //找不到返回-1
      }
    </script>
  </body>
</html>
